package com.zk.algorithm.linkedlist;

import com.zk.algorithm.annotation.Easy;
import com.zk.algorithm.annotation.LeetCodeExplore;
import com.zk.algorithm.bean.ListNode;

/**
 * @author zk
 */
@LeetCodeExplore
@Easy
public class RemoveNthNodeFromEndOfList {

    //            fast
    //             ↓
    // 1->2->3->4->5
    //       ↑
    //      slow
    //
    // 假设 n == 2
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // DUMMY: 方便处理 head == null 的问题
        // DUMMY -> 1 -> 2 -> 3 -> 4 -> 5
        ListNode dummy = new ListNode(0);
        ListNode slow = dummy,
                fast = dummy;
        slow.next = head;

        // Move fast in front so that the gap between slow and fast becomes n
        // DUMMY -> 1 -> 2 -> 3 -> 4 -> 5
        //                    ↑
        //                  fast (移动了 n+1 步)
        for (int i = 1; i <= n + 1; i++) {
            fast = fast.next;
        }

        // Move fast to the end, maintaining the gap
        // DUMMY -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
        //                                    ↑
        //                                  fast
        //                    ↑
        //                  slow
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }

        // Skip the desired node
        slow.next = slow.next.next;

        // 返回头指针
        return dummy.next;
    }

}
